package graph.unweighted.bfs.loopDetection;

import graph.unweighted.CandyGraph;
import queue.CandyLoopQueue;

/**
 * 
 * @Title: LoopDetect.java 
 * @Package graph.dfs.demo3 
 * @Description: 使用BFS完成图的环检测
 * @author CandyWall   
 * @date 2021年1月15日 下午1:26:00 
 * @version V1.0
 */
public class CandyLoopDetection {
    private CandyGraph graph;
    private int[] colors;  //记录顶点是否被遍历过，默认都为false
    private final int WHITE = 1;
    private final int GRAY = 1;
    private final int BLACK = 2;
    public CandyLoopDetection(CandyGraph graph) {
        this.graph = graph;
        colors = new int[graph.getVertex_num()];
        for(int i = 0; i < graph.getVertex_num(); i++) {
            colors[i] = WHITE;
        }
        // System.out.println("当前树是否有环：" + hasLoop());
    }
    
    /**
     * 判断当前图中是否有环
     * @return
     */
    public boolean hasLoop() {
        for(int v = 0; v < graph.getVertex_num(); v++) {
            if(colors[v] == WHITE) {
                if(bfs(v)) {
                    return true;
                }
            }
        }
        return false;
    }
    
    /**
     * 计算当前图中环的数量：需要在dfs的else if中添加条件：v != prev，
     * 否则，可能会在第一次递归的时候检测到假环
     * @return
     */
    public int getLoopCount() {
        int count = 0;
        for(int v = 0; v < graph.getVertex_num(); v++) {
            if(colors[v] == WHITE) {
                if(bfs(v)) {
                    count++;
                }
            }
        }
        return count;
    }
    /**
     * 广度优先遍历：从顶点v出发，判断图中是否有环
     */
    private boolean bfs(int s) {
        CandyLoopQueue<Integer> queue = new CandyLoopQueue<>();
        queue.enqueue(s);
        colors[s] = GRAY;
        while(!queue.isEmpty()) {
            int v = queue.dequeue();
            for(int w : graph.adjacentVertexes(v)) {
                if(colors[w] == WHITE) {
                    queue.enqueue(w);
                    colors[w] = GRAY;
                }
                // 如果遍历过了，并且不是当前节点的上一个节点
                else if(colors[w] == GRAY) {
                    return true;
                }
            }
            colors[v] = BLACK;
        }
        return false;
    }
    
    public static void main(String[] args) {
        CandyGraph graph1 = new CandyGraph("testData/graph/graph.txt");
        CandyLoopDetection loopDetect1 = new CandyLoopDetection(graph1);
        System.out.println("当前图中环的数量：" + loopDetect1.getLoopCount());
        CandyGraph graph2 = new CandyGraph("testData/graph/dfs/demo3/graph.txt");
        CandyLoopDetection loopDetect2 = new CandyLoopDetection(graph2);
        System.out.println("当前图中环的数量：" + loopDetect2.getLoopCount());
    }
}
